package com.example.leetcode.trainingcamp.week5.Thursday;

/**
 * 编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
 *
 * <p>每行中的整数从左到右按升序排列。 每行的第一个整数大于前一行的最后一个整数。
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/search-a-2d-matrix
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Test74 {

    public boolean searchMatrix(int[][] matrix, int target) {
        int len1 = matrix.length;
        for (int i =0;i<len1;i++){
            boolean b = findTarget(matrix[i], target);
            if (b) return true;
        }
        return false;
    }

    public boolean findTarget(int[] nums,int target){
        int high = nums.length-1;
        int low = 0;
        while (low <= high){
            int mid = low + (high -low) / 2;
            if (nums[mid] == target) return true;
            if (nums[mid] < target) low = mid + 1;
            if (nums[mid] > target) high = mid - 1 ;
        }
        return false;
    }
}


class Demo74{
  public static void main(String[] args) {
    int[][] matrix = {{1},{3}};
    int target = 3;
    Test74 t = new Test74();
    System.out.println(t.searchMatrix(matrix, target));
  }
}